package homework4;

/**
 * Longest Increased Sequence
 * 
 * @author eDisOn
 * 
 */
public class LIS
{
	String result = "";

	public int calcLIS(int[] arr, int[] prefix, int[] indexer)
	{
		int len = 1;

		// record is used to record the minimum latest item in the LIS
		int[] record = new int[arr.length + 1];
		record[1] = arr[0];

		int start = 1, mid, end = len;
		for (int i = 1; i < arr.length; i++)
		{
			start = 1;
			end = len;

			// binary search the longest sequence in the record
			while (start <= end)
			{
				mid = (start + end) >> 1;
				if (record[mid] <= arr[i])
					start = mid + 1;
				else
					end = mid - 1;
			}

			// update length if needed
			if (start > len)
				len = start;

			// trace the prefix of current LIS
			record[start] = arr[i];
			indexer[start] = i;
			prefix[i] = indexer[start - 1];
		}
		return len;
	}

	public String printLIS(int[] arr, int[] prefix, int len, int end)
	{
		result = "";
		result += "***The longest increased sequence length is: " + len
				+ "***\n";
		result += "[";
		print(arr, prefix, end);
		result = result.substring(0, result.length() - 1) + "]";

		return result;
	}

	private void print(int[] arr, int[] prefix, int end)
	{
		int elem = arr[end];
		end = prefix[end];
		if (end > -1)
		{
			print(arr, prefix, end);
		}
		result += elem + ",";
	}

	// public static void main(String[] args)
	// {
	// LIS lis = new LIS();
	// int[] arr = new int[] { 31, 1 };
	// int[] prefix = new int[arr.length];
	// for (int i = 0; i < prefix.length; i++)
	// {
	// prefix[i] = -1;
	// }
	// int[] indexer = new int[arr.length + 1];
	// indexer[0] = -1;
	// int len = lis.calcLIS(arr, prefix, indexer);
	// System.out.println(lis.printLIS(arr, prefix, len, indexer[len]));
	// }
}